#include <stdio.h>

#define MaxSize 100
typedef int KeyType;
typedef char ElemType;
typedef struct {
    KeyType key;   // 存放关键字,KeyType为关键字类型
    ElemType data; // 其他数据,ElemType为其他数据的类型
} SqType;

int k = 1;
void QuickSort(SqType R[], int s, int t) { // 对R[s]至R[t]的元素进行快速排序
    int i = s, j = t;
    SqType tmp;
    if (s < t) {        // 区间内至少存在一个元素的情况
        tmp = R[s];     // 用区间的第1个元素作为基准
        while (i < j) { // 从区间两端交替向中间扫描,直至i=j为止
            while (j > i && R[j].key >= tmp.key)
                j--; // 从右向左扫描,找第1个关键字小于tmp.key的R[j]
            if (i < j) {
                R[i] = R[j]; // 将R[j]前移到R[i]的位置
                i++;
            }
            while (i < j && R[i].key <= tmp.key)
                i++; // 从左向右扫描,找第1个关键字大于tmp.key的元素R[i]
            if (i < j) {
                R[j] = R[i]; // 将R[i]后移到R[j]的位置
                j--;
            }
        }
        R[i] = tmp;
        printf("第%d次划分: ", k++); // 输出一趟排序结果
        for (int a = 0; a < 10; a++)
            printf("%3d", R[a].key);
        printf("\n");
        QuickSort(R, s, i - 1); // 对左区间递归排序
        QuickSort(R, i + 1, t); // 对右区间递归排序
    }
}

// 快速排序
#include "sort_base.cpp" //包含排序基础工具

// 划分
/* 哨兵划分 */
int partition(SqType R[], int left, int right) {
    // 以 nums[left] 为基准数
    int i = left, j = right;
    SqType tmp = R[left]; // 基准数
    while (i < j) {
        while (i < j && R[j].key >= tmp.key)
            j--; // 从右向左找首个小于基准数的元素
        if (i < j) {
            R[i] = R[j]; // 将R[j]前移到R[i]的位置
            i++;
        }
        while (i < j && R[i].key <= tmp.key)
            i++; // 从左向右找首个大于基准数的元素
        if (i < j) {
            R[j] = R[i]; // 将R[i]后移到R[j]的位置
            j--;
        }
    }
    R[i] = tmp;
    return i; // 返回基准数的索引
}

void print(SqType R[], int left, int right) {
    static int p = 0;
    printf("p=%2d: ", p++); // 输出一趟排序结果
    for (int i = 0; i < left; i++) {
        printf("   "); // 输出空格
    }
    for (int i = left; i <= right; i++) {
        printf("%3d", R[i].key);
    }
    printf("\n");
}

/* 快速排序 */
void quick_sort(SqType R[], int left, int right) {
    // 子数组长度为 1 时终止递归
    if (left >= right)
        return;
    // 哨兵划分
    int pivot = partition(R, left, right);

    print(R, left, right); // 输出当前划分结果

    // 递归左子数组、右子数组
    quick_sort(R, left, pivot - 1);
    quick_sort(R, pivot + 1, right);
}

int main() {
    SqType R[MaxSize];
    KeyType A[] = {75, 87, 68, 92, 88, 61, 77, 96, 80, 72};
    int i, n = 10;

    for (i = 0; i < n; i++)
        R[i].key = A[i];

    printf("初始数据: \n");
    print_pass(-1, R, n);    // 输出初始数据
    quick_sort(R, 0, n - 1); // 调用快速排序函数

    // QuickSort(R, 0, n - 1);

    printf("排序结果:\n");
    print_pass(99, R, n);

    // for (i = 0; i < n; i++)
    //     printf("%3d", R[i].key);
    // printf("\n");
    return 0;
}
